A common practice in the computer software industry is to update binary code by way of a patch. Application of a patch to existing binary code results in updated binary code. In its simplest form, a patch is a set of commands for creating the updated binary code using the existing binary code. For example, the patch may include a set of copy and insert commands. A copy command includes a reference to a section of the existing binary code that matches a section of the updated binary code. The copy command is useful when a portion of the updated binary code can be obtained from the existing binary code. An insert command provides data to be inserted in the updated binary code. The insert command is used to create portions of the updated binary code that cannot be found in the existing binary code.
In practice, the “copy” command in a patch rarely involves copying an exact portion of the existing binary code for inclusion in the updated binary code. Usually, the “copied” portion of the existing binary code is similar, but not exactly the same, as the desired portion of updated binary code. Accordingly, the patch may also include an associated difference file. The copy command is used to indicate that a portion of the updated binary code is similar to the existing binary code, and the associated difference file contains the byte-wise differences. Each copy command may specify an offset in the existing binary code and a length. The specified portion of the existing binary code is read and added to the same number of bytes from the associated difference file to create the desired portion of the updated binary code.
The creation of a patch is typically a two-step process. The first step is to identify the similar regions between a new binary image and an old binary image. This is an indexing step that involves searching through the two images to find regions that are the same or substantially similar. In some cases this indexing operation may be based upon hashing or suffix sorting. These types of operations are very computationally intensive. The indexing operation results in an index file that contains pointers or other information defining the regions of substantial similarity between the new image and the old image. In some instances the index file may be referred to as a similar regions map.
After the indexing operation, a patch generation operation constructs the patch by generating “copy” and “insert” commands based upon the new image, the old image and the similar regions map (i.e. the index file). The result of the patch generation operation is the patch file.
In some instances, it may be desirable to “undo” or rollback a patch, so as to recover the old binary image. One method of doing this is to save a copy of the old image in memory; however, this is impractical on memory-scarce devices, like mobile handheld devices. Another method of undoing a patch is to distribute the patch along with a reverse patch, which can be used by the device to recover the old image from the new image. However, the reverse patch may be a large file which makes the downloading of both the forward patch and the reverse patch a time consuming and possibly expensive operation. A third method is to have the device generate the reverse patch when it applies the forward patch, so as to be able to undo the changes; however, computing a patch is a computationally intensive operation which the device may be unable to practically accomplish given its limited memory and processing power.
It would be advantageous to provide a new method and system for generating a reverse patch.
Similar reference numerals may have been used in different figures to denote similar components.